MAX_INT = 101


class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        size = len(s)

        # dp[k][i][j] = 将[i,j]切分为k个的最小字符数
        dp = [[[MAX_INT] * size for _ in range(size)] for _ in range(k + 1)]

        # 计算当k=1时所需的最小字符数
        for i in range(size):
            dp[1][i][i] = 0
        for i in range(size - 1):
            dp[1][i][i + 1] = 0 if s[i] == s[i + 1] else 1
        for length in range(2, size):
            for i in range(size - length):
                j = i + length
                dp[1][i][j] = dp[1][i + 1][j - 1] + (0 if s[i] == s[j] else 1)

        # print("状态矩阵:", "k", "=", 1)
        # for row in dp[1]:
        #     print(row)

        for kk in range(2, k + 1):
            for length in range(1, size):
                for i in range(size - length):
                    j = i + length
                    dp[kk][i][j] = min(dp[1][i][t] + dp[kk - 1][t + 1][j] for t in range(i, j))

            # print("状态矩阵:", "k", "=", kk)
            # for row in dp[kk]:
            #     print(row)

        return dp[k][0][-1]


if __name__ == "__main__":
    print(Solution().palindromePartition("abc", 2))  # 1
    print(Solution().palindromePartition("abc", 3))  # 0
    print(Solution().palindromePartition("leetcode", 8))  # 0
